package com.note.feng.leetcode.algorithms.easy.seven;

import java.util.ArrayList;
import java.util.List;

public class SevenHundredTwentyEight {
    /**
     * 728 自除数
     * 自除数 是指可以被它包含的每一位数整除的数。
     *
     * 例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
     * 自除数 不允许包含 0 。
     *
     * 给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right] 内所有的 自除数 。
     *
     * 示例 1：
     *
     * 输入：left = 1, right = 22
     * 输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
     * 示例 2:
     *
     * 输入：left = 47, right = 85
     * 输出：[48,55,66,77]
     *  
     * 提示：
     *
     * 1 <= left <= right <= 104
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/self-dividing-numbers
     */
    /**
     * 解法：直接判断
     * 依次遍历区间内的数字，
     * 自除数判断：取余 10 ，得到最后一位数字；除以 10，再取余 10，得到第二位数字。。。。
     * 得到每位数字后，再对其取余，判断是否为 0
     * @param left
     * @param right
     * @return
     */
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> list = new ArrayList<>();
        while (left <= right){
            if(dfs(left)){
                list.add(left);
            }
            left ++;
        }
        return list;
    }

    private boolean dfs(int n){
        int num = n;
        while (num != 0){
            int a = num % 10;
            if(a == 0 || n % a != 0){
                return false;
            }
            num = num / 10;
        }
        return true;
    }

    public static void main(String[] args) {
        SevenHundredTwentyEight s = new SevenHundredTwentyEight();
        System.out.println(s.dfs(129));
    }
}
